home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2604 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.4 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: red/black trees ?
  5. Date: 22 Jan 1996 08:26:38 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4e0druINN5fn@keats.ugrad.cs.ubc.ca>
  8. References: <DLBpME.48G@gil.com.au>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <DLBpME.48G@gil.com.au>,
  12. Simon Knight <simnight@gil.ipswichcity.qld.gov.au> wrote:
  13. >Red/black trees have been mentioned in a number of magazines I have
  14. >read recently. Does anyone know what the algorithm is? How do they
  15. >compare with 2-3 trees, splay trees etc.
  16.  
  17. I don't know how they compare.
  18.  
  19. Most of the operations for red-black trees are O(log n), where n is the size of
  20. the data that you are putting into the tree. These operations include
  21. insertion, deletion and finding the maximum/minimum node according to the
  22. tree's order.
  23.  
  24. The red-black method assures that the tree is always sufficiently balanced so
  25. that the deepest node is never more than twice as deep as the shallowest node.
  26. This still gives you O(log n) behavior, but with better constants than AVL
  27. trees. The reason is than an AVL tree, although having more "perfect"
  28. balancing, requires more overhead to maintain.
  29.  
  30. Due to the O(log n) of insertion, and of finding and deleting the highest node,
  31. you can use a r/b tree as a priority queue implementation instead of a heap.
  32. -- 
  33.  
  34.